%# -*- coding: utf-8-unix -*-
%%==================================================
%% chapter05.tex for BJTU Master Thesis
%%==================================================

%\bibliographystyle{bjtu}%[此处用于每章都生产参考文献]
\chapter{基于动态投标价格的铁路动态价格建模与算法} \label{chap:Chapter4}

投标价格是制定客运产品动态价格的一种方式。本章研究的问题是如何确定每个列车服务区间的动态投标价格。随着旅客对换乘出行理念的不断接受，越来越多的旅客开始自行或者借助 12306 网站的路径规划功能规划换乘出行路线。针对价格敏感度较高的客运市场，在制定动态投标价格时需要考虑旅客换乘对客票销售的影响。

\section{问题特点}

\subsection{旅客换乘}

为了考虑旅客通过换乘的方式出行，需要对第二章提出的建模框架进行一些拓展。在第二章中仅考虑了旅客在一个备选的产品集合中选择一个产品的情况。而在旅客可以选择换乘的前提下，旅客可以选择多个产品出行。为此，在本章中引入了旅客的出行路径的概念，一条旅客的出行路径可以由一个或者多个产品实现。下面举例说明。

\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{Fig_4-1.png}
\bicaption[fig:4-1]{例子4-1示意图}{例子4-1示意图}{Fig}{An illustration for example 4-1}
\end{figure}

\textbf{例4-1. 考虑旅客换乘的铁路网络}

在由三个车站A、B、C组成的铁路网络上，运行了两列车。列车1从A站发往B站，列车2从A站经停B站到达C站。案例网络如图\ref{fig:4-1}所示。表\ref{tab:4-1}和表\ref{tab:4-2}列举了本例中的列车服务区段、产品及其价格信息（其中每个产品价格固定）。

\begin{table}[!h]
	\centering %居中	
	\bicaption[tab:4-1]{列车服务区段表}{列车服务区段表}{Table}{List of train segment in Example 4-1}
	\begin{tabular}{p{1cm}<{\centering}p{3cm}<{\centering}p{2cm}<{\centering}p{2cm}<{\centering}}
		\hline
		序号 & 列车    & 起点 & 终点 \\ \hline
		1  & 列车 1 & A  & B  \\ 
		2  & 列车 2 & A  & B  \\ 
		3  & 列车 2 & B  & C  \\ \hline
	\end{tabular}
\end{table}

\begin{table}[!h]
	\centering
	\bicaption[tab:4-2]{产品列表}{产品列表}{Table}{List of products in Example 4-1}
	\begin{tabular}{ccccc}
		\hline
		序号 & 起点 & 终点 & 列车服务区段 & 价格 \\ \hline
		1  & A  & B  & 1     & 40 \\ 
		2  & A  & B  & 2     & 50 \\ 
		3  & B  & C  & 3     & 60 \\ 
		4  & A  & C  & 2,3   & 80 \\ \hline
	\end{tabular}
\end{table}

表\ref{tab:4-3}列举了本例中旅客所有的可能出行路径。其中路径5需要旅客换乘，即选择了路径5的旅客需要在B站从列车1下车换上列车2。

\begin{table}[!h]
	\centering %居中
	\bicaption[tab:4-3]{产品列表}{产品列表}{Table}{List of itineraries in Example 4-1}
	\begin{tabular}{cccccc}
		\hline
		序号 & 起点 & 终点 & 产品编号 & 是否换乘 & 价格  \\ \hline
		1  & A  & B  & 1    & 否    & 40  \\ 
		2  & A  & B  & 2    & 否    & 50  \\ 
		3  & B  & C  & 3    & 否    & 60  \\ 
		4  & A  & C  & 4    & 否    & 80  \\ 
		5  & A  & C  & 1,3  & 是    & 100 \\ \hline
	\end{tabular}
\end{table}

\subsection{动态投标价格}

投标价格机制是通过为每个存量单位设置一个价格阈值来控制产品-价格开发与否的客票销售规则。在第一章中介绍了投标价格的基本原理。在例4-1中，假设列车服务区段的投标价格分别为10,40,50时，产品的开闭状态如表\ref{tab:4-14}所示。

\begin{table}[!h]
	\centering
	\bicaption[tab:4-14]{产品可售情况}{产品可售情况}{Table}{Availbility of products in Example 4-1}
	\begin{tabular}{ccccccc}
		\hline
		产品编号 & 起点 & 终点 & 列车服务区段 & 价格 & 投标价格 & 是否可售 \\ \hline
		1  & A  & B  & 1      & 40 & 10   & 可售   \\ 
		2  & A  & B  & 2      & 50 & 40   & 可售   \\ 
		3  & B  & C  & 3      & 60 & 50   & 可售   \\ 
		4  & A  & C  & 2,3    & 80 & 90   & 不可售   \\ \hline
	\end{tabular}
\end{table}

动态的投标价格机制就是设置一个根据时间变化的价格阈值（时变的投标价格）。在静态的投标价格机制下，产品-价格在预售期的开始开放得数量最多，随着车票不断售出，可售的产品-价格会越来越少。而动态的投标价格则更加灵活，可以随时调控产品-价格的可售状态。同时随着客票销售系统的不断发展并逐步网络化，客票销售的实时性也越来越强。而通过投标价格的方式，可以实时地控制产品的销售。本章研究的问题就是在实时售票系统下制定动态价格。

另外，本章考虑的按照列车服务区段来制定动态投标价格，即同一列车服务区段对应的存量单位的投标价格在任何时间都是相同的，为表达简便，下文将直接用“列车服务区段的投标价格”表示。

\section{动态投标价格模型} 

在明确了问题的特点之后，接下来要结合第二章的建模框架研究如何确定动态投标价格。本章的采用的符号如表\ref{tab:4-4}所示。

所有列车服务区段的集合用 $I$ 表示，用 $i \in I$ 索引。对于某一列车服务区段 $i$，其所包含的存量单位用 $m \in i$ 索引。在文献\parencite{MeissnerStrauss-522,ZhangAdelman-518,Koch-605}中，对应的概念被称为“资源(Resource)”。

列车服务区段的剩余存量单位数量用 ${x_i}$ 表达。本章用 $\boldsymbol{x}$ 表示列车服务区段剩余数量向量。在预售期开始前，它的初始值用 $\boldsymbol{c}$ 表示。产品-价格的表达与第二章中定义的相同，产品-价格集合用$J$表示，用$j \in J$ 索引。产品-价格$j$ 的售价用 $r_j$ 表示。

在考虑换乘的条件下，旅客在出行时可能购买多张车票，旅客的出行路径可以看作是一张或一个车票序列。令 $K$ 表示所有可能的旅客路径，用$k \in K$索引。需要注意的是，这里的路径不包含同一产品对应的两张的车票。令 $\boldsymbol{A}$ 表示列车服务区段与路径的关系矩阵，如果列车服务区段 $i$ 属于构成路径 $k$ 的任一产品，那么 ${{a}_{i,k}}=1$；否则，有 ${{a}_{i,k}}=0$。矩阵 $A$ 的第 $k$ 列记为 $A^k$，它表示路径 $k$ 使用的列车服务区段情况。 路径 $k$ 的费用（选择路径 $k$ 出行需要的购票费用）记为 $\sum\limits_{j \in k} {{r_j}} $。

\begin{table}[!htb]
\centering %居中
\bicaption[tab:4-4]{符号列表}{符号列表}{Table}{Symbol list}
\begin{tabular}{ll}
	\hline
	符号                                                    & 含义                                                          \\ \hline
	$I$                                                   & 所有列车服务区段的集合，通过 $i$ 索引                                       \\
	$J$                                                   & 产品-价格的集合，通过 $j$ 索引                                          \\
	$K$                                                   & 旅客所有可能的出行路径集合，通过 $k$ 索引                                     \\
	$L$                                                   & 细分市场的集合，通过 $l$ 索引                                           \\
	$X$                                                   & 每个列车服务区段存量剩余的状态空间，通过状态变量$ {\boldsymbol{x}}$ 索引              \\
	$U$                                                   & 所有产品-价格开放的状态构成的决策空间，通过决策变量 ${\boldsymbol{u}}$索引             \\
	$T$                                                   & 离散的时间段数量，通过$t = 1, \ldots ,T $索引                            \\
	$D_\alpha$                                            & 在 $t = \alpha$之前的时间段的集合，通过 $d$ 索引                           \\
	$K_l$                                                 & 细分市场 $l$ 的旅客所有路径                                            \\
	${P'_{l,k}}\left( {\boldsymbol{u}} \right)$           & 细分市场 $l$ 的旅客在产品-价格开放状态为 ${\boldsymbol{u}}$ 的情况下选择路径 $k$ \\
	& 的概率 \\
	$P_{t,k}\left( {\boldsymbol{u}} \right)$              & 在时间段 $t$ 产品-价格开放状态为 ${\boldsymbol{u}}$ 的情况下旅客选择路径 $k$ 的概率   \\
	${\mathcal{{\cal F}}\left( {\boldsymbol{u}} \right)}$ & 在产品-价格开放状态为 ${\boldsymbol{u}}$ 时，开放的产品-价格对应的列车服务区段          \\
	${{\rho _t}}$                                         & 在时间段 $t$ 有旅客到达的概率                                           \\
	${\lambda_{t,l}}$                                     & 在时间段 $t$ 到达的旅客属于细分市场 $l$ 的概率                                \\
	${r_j}$                                               & 产品-价格 $j$ 的售价                                               \\
	${v_t}\left( {{{\boldsymbol{x}}_t}} \right)$          & 在时间段 $t$ 状态为 ${\boldsymbol{x}}_t$ 的情况下最大的累计收益期望             \\
	${\pi _{t,i}}$                                        & 列车服务区段 $i$ 在时间段 $t$ 的投标价格                                   \\
	$\varphi \left( d \right)$                            & 时间间隔 $d$ 的第一个时间段                                            \\
	${\delta \left( t \right)}$                           & 时间段 $t$ 从属的时间间隔                                             \\
	$\mathbf{A}$                                          & 列车服务区段和旅客路径的关系矩阵                                            \\
	${\boldsymbol{u}}$                                    & 在时间段 $t$ 的产品开放决策                                            \\
	${{{\boldsymbol{e}}_i}}$                              & 列车服务区段 $i$ 对应的单位资源向量                                        \\
	${\boldsymbol{x}}_t$                                  & 在时间段 $t$ 开始时每个列车服务区段存量剩余向量，状态变量                             \\
	$\boldsymbol{c}$                                      & 在预售期开始时每个列车服务区段存量剩余向量                                       \\ \hline
\end{tabular}
\end{table}

\subsection{客票销售决策模型}

本节考虑的是实时的动态价格，也就是说，投标价格可以在极短的时间内发生变化。按照第二章的建模思路，客票销售决策过程是一个有限离散时间过程。实时的控制问题可以描述为售票阶段数$N$非常大的问题，记为“$N=\infty$”型问题。在这类问题中，由于售票参数可以被实时调整，可以认为每个旅客购票之间都至少进行了一次客票销售决策，也即客票销售过程模型的形式退化为单阶段的马尔科夫链模型，如图\ref{fig:2-4}所示。

\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{Fig_2-4.png}
\bicaption[fig:2-4]{实时问题模型}{实时问题模型}{Fig}{Real-time model}
\end{figure}

在“$N=\infty$”型问题中，$S_n$到$S_{n+1}$的状态转移和一个阶段内的收入$R_n$的形式简单，可以直接写出。所以本章不再引入旅客购票过程模型\footnote{为表述方便，本章统一采用$t$作为离散时间的索引，不再使用符号$n$与$N$。}。假设预售期被分为$T$个离散的时间段，$t = 1,2,3...,T$。令$\pi _{t,i}$表示时变的列车服务区段 $i$ 在时间段 $t$ 的投标价格。动态投标价格的机制可以表示为，如果 ${r_j} \ge \sum\limits_{i \in j} \pi _{t,i}$ 并且 ${x_{t,i}} \ge {0}\;\;\;\forall i \in j$，且有足够的存量单位，产品-价格 $j$ 是开放的，反之关闭。在时间段 $t$，如果先忽略席位一致性的约束，则可以认为，只要一个产品-价格$j$需要的列车服务区段的存量剩余都大于0，且确定了投标价格为${\pi _{t,i}}$，那么此时产品-价格开放情况 $\boldsymbol{u}_t$ 就由式(\ref{eq:4-26})表示。

\begin{equation}
u_j =\left\{\begin{array}{ll}
{1} & {\text { if } {{x_{t,i}} > 0,\;\forall i \in I_j} \text{ 并且 } {r_j} \ge \sum\limits_{i \in I_j} {{\pi _{t,i}}}} \\ 
{0} & {\text { 其他 }}
\end{array}
\right.
\label{eq:4-26}
\end{equation}

本章的动态投标价格问题可以表述为：在$\left( {{I,J,K}} \right)$ 固定的条件下，对于每个时间段 $t$，都要确定 ${\pi _{t,i}}, \forall i \in I$ 的值，使得售票总收益最高。根据第二章的建模框架，客票销售决策过程模型的形式可以写为以下形式：

\begin{flalign}
&{V_t}\left( {\boldsymbol{x}}_t \right) = \mathop {\max }\limits_{ \boldsymbol{\pi} } \left\{ {\sum\limits_{k \in {K}} {{P_{t,k}}\left( {{\boldsymbol{u}_t}} \right)\left[ {\sum\limits_{j \in J_k} {{r_j} + {v_{t + {1}}}\left( {{{\boldsymbol{x}}_t} - {{\boldsymbol{A}}^k}} \right)} } \right]}  + \left( {{1} - \sum\limits_{k \in {K}} {{P_{t,k}}\left( {{\boldsymbol{u}_t}} \right)} } \right){V_{t + 1}}\left( {\boldsymbol{x}_t} \right)} \right\}
\label{eq:4-2} \\
&{\text{边界条件为}}: \nonumber \\
&{V_t}\left( \boldsymbol{0} \right) = 0\;\;\;\forall t = 1, \ldots ,T 
\label{eq:4-3}\\
&V_{T + 1} \left( \boldsymbol{x}_{T + 1} \right) = 0 \;\;\;\forall {\boldsymbol{x}_{T + 1}} \in {X} \label{eq:4-4}
\end{flalign}

其中，${P_{t,k}} \left( \boldsymbol{u}_t \right)$ 表示在 $\boldsymbol{u}_t$ 下路径 $k$ 在时间段 $t$ 内被旅客选择的概率，它的值由旅客行为模型确定。在时间段$t$，对于给定的 $\boldsymbol{x}_t$，如果所有旅客的备选路径都可行，则下一阶段的状态 $\boldsymbol{x}_{t + 1}$ 共有 $|K|+1$ 种可能。

%贝尔曼方程 (\ref{eq:4-2}) 提出了一个递归的视角去求解 ${V_t}\left( {{{\boldsymbol{x}}_t}} \right)$. 
%图\ref{fig:4-2}展示了动态规划模型的状态变化。
%\begin{figure}[htb]
%\centering
%\includegraphics[width=0.6\textwidth]{Fig_4-2.png}
%\bicaption[fig:4-2]{动态规划模型示意}{动态规划模型示意}{Fig}{An illustration of dynamic programming model}
%\end{figure}

\subsection{旅客行为模型}

本章使用的旅客行为模型与第二章中提到的旅客行为模型最大的不同点在于，旅客是从一个可行的路径备选集合中选择出行路径，而非选择单一产品。旅客行为模型的其它部分与之前相同。市场的集合用$L$表示，子市场用$l \in L$索引。令子市场 $l$ 的旅客在产品-价格开放情况 $\boldsymbol{u}$ 下选择路径 $k$ 的概率记为${P'_{l,k}}\left( \boldsymbol{u} \right)$。

通过引入市场细分，${P_{t,k}} \left( {\boldsymbol{u}_t} \right)$ 可以通过式(\ref{eq:4-5})计算。其中旅客的排队购票的过程仍然通近似过泊松流表示，其强度表示为${\rho_t}$。对于一个在时间段 $t$ 到达的旅客，其属于子市场 $l$ 的概率为$\lambda_{t,l}$。
\begin{equation}
{P_{t,k}}\left( {{\boldsymbol{u}_t}} \right) = \sum\limits_{l \in L} {{\rho _t}} {\lambda_{t,l}}{P'_{l,k}}\left( {{\boldsymbol{u}_t}} \right)
\label{eq:4-5}	
\end{equation}

本章对旅客的选择行为还是采用Logit模型，${P'_{l,k}}\left( \boldsymbol{u} \right)$的取值如式(\ref{eq:4-1})所示。

\begin{equation}
{P'_{l,k}}\left( \boldsymbol{u} \right) = \frac{{\beta_k^l\sum\limits_{j \in J_h}u_j}}{{\sum\limits_{h \in {K_l}} {\beta_h^l \sum\limits_{j \in J_h}u_j }+{ \beta_\emptyset ^l} }}
\label{eq:4-1}
\end{equation}
\begin{itemize}
	\item ${\beta_k^l}$ 表示子市场$l$的旅客对路径$k$的效用，${\beta_\emptyset ^l}$ 则表示放弃购票的效用。
	\item $K_l \subset {K}$ 表示子市场 $l$旅客所考虑的所有路径集合。如果 $k \notin {K_l}$，则 ${\beta_k^l} = 0$.
	\item $J_h$ 表示在路径$h$需要使用的产品-价格的集合。
\end{itemize}

\section{问题的转化与求解}

通过求解式(\ref{eq:4-2})，可以得到整个预售期的动态投标价格$\boldsymbol{\pi}$。然而在求解过程中，仍然会遇到“维数灾难”，导致问题无法通过遍历状态空间而求解。本节考虑采用近似的方法进行求解。

\subsection{问题近似}

在本章中，通过引入动态投标价格控制机制，带入到客票销售决策模型中得到式(\ref{eq:4-2})以确定动态投标价格。然而在其它大量关于投标价格研究中，它通常是由直接决定产品-价格开闭的控制机制的模型中引入。以文献\parencite{TalluriRyzin-457}为例，在他们的研究中，将$\boldsymbol{u}_t$作为决策变量来研究最优控制问题，其贝尔曼方程如下所示。

\begin{flalign}
&{V_t}\left( {{{\boldsymbol{x}}_t}} \right) = \mathop {\max }\limits_{ \boldsymbol{u}_t \in N(\boldsymbol{x}_t) } \left\{ {\sum\limits_{k \in {K}} {{P_{t,k}}\left( {{\boldsymbol{u}_t}} \right)\left[ {\sum\limits_{j \in J_k} {{r_j} + {V_{t + {1}}}\left( {\boldsymbol{x}_t - {{\boldsymbol{A}}^k}} \right)} } \right]}  + \left( {1 - \sum\limits_{k \in {K}} {P_{t,k}}\left( \boldsymbol{u}_t \right) } \right){V_{t + {{1}}}}\left( {\boldsymbol{x}}_t \right)} \right\}
\nonumber \\
&\hspace{1cm} = \mathop {\max }\limits_{\boldsymbol{u}_t \subset N\left( {{\boldsymbol{x}_t}} \right)} \left\{ {\sum\limits_{k \in {K}} {{P_{t,k}}\left(  \boldsymbol{u}_t \right)\left[ {\sum\limits_{j \in k} {r_j - \left( {V_{t + 1}\left( \boldsymbol{x}_t \right) - {V_{t + 1}}\left( {{{\boldsymbol{x}}_t} - {{\boldsymbol{A}}^k}} \right)} \right)} } \right]}  + {V_{t + 1}}\left( {{{\boldsymbol{x}}_t}} \right)} \right\} \nonumber \\
&\hspace{2cm}\forall t,{{\boldsymbol{x}}_t} \nonumber
\end{flalign}

其中 $\boldsymbol{u}_t$ 受限于当前的存量单位的限制，即${\boldsymbol{u}_t} \in N\left( {\boldsymbol{x_t}} \right)$, 其中 $N\left( {\boldsymbol{x_t}} \right) = \left\{ {j \left| {{x_{t,i}} > 0,\;\forall i \in I_j} \right.} \right\}$。

以上问题和式(\ref{eq:4-2})的问题最大的不同点在于问题背后采用的客票销售规则是不同的，该问题反映的客票销售规则是直接决策开放产品。在第一章中介绍过，通常实时地决策是难以实现的，所以需要通过客票销售规则间接地控制客票的销售。但是这个过程可以在理论上通过上式表达。而这个问题的最优解也是采用其它客票销售规则的一个上界。因为它可以遍历所有的产品-价格的开放的可能情况，而间接的客票销售规则不能。也就是说如果可以求得此问题的解，那么至少可以得到原问题的一个上界。

为了求解此问题，这里采用第二章中提到的近似动态规划的思想。通过引入形式如(\ref{eq:4-6})所示的仿射近似值函数，值函数可以被理解为存量单位的边际成本之和加上一个常数项。

\begin{equation}
{\bar V_t}\left( {{{\boldsymbol{x}}_t}} \right) = {\theta _t} + \sum\limits_i {{\pi _{t,i}}{x_i}} , \ {\theta _t} \ge {{0}}, {\pi _{t,i}} \ge {{0}} \;
\label{eq:4-6}
\end{equation}

在式(\ref{eq:4-6})中，$\theta _t$是常数项，$\pi _{t,i}$是列车服务区间的存量单位的边际成本。它被称为边际成本是因为根据式(\ref{eq:4-6})有${\pi _{t,i}} = {\bar V_{t + 1}}\left( \boldsymbol{x}_t \right) - \bar V_{t + 1} \left( {{{\boldsymbol{x}}_t} - {{\boldsymbol{e}}_i}} \right)$，所以$\pi _{t,i}$也被理解为列车服务区段$i$的机会成本。其中${{{\boldsymbol{e}}_i}}$ 是$i$的列车服务区段单位向量。${V_t}\left( {{{\boldsymbol{x}}_t}} \right)$ 表示 ${\boldsymbol{x}}_t$ 在时间段 $t$ 的最大收益期望，它可以通过求解式(\ref{eq:4-2})得到。

通过值函数近似，问题转化为了确定参数$\theta _t$和$\pi _{t,i}$。本章要采用第二章中提到的基于规划的标定这两个参数。首先要将动态规划问题形式转化为线性规划问题形式，其中约束和数量取决于$X$和$U$的规模，它们受到列车区段、列车席位数和产品-价格数量的影响。

\begin{align*}
&{\text{LP}}: \mathop {\min }\limits_{\left\{ {{\bar V_t}\left(  \cdot  \right)} \right\}\;\forall t} {\bar V_1}\left( {\boldsymbol{c}} \right) \\
&\text{s.t.} \\
&{\bar V_t}\left( {{{\boldsymbol{x}}_t}} \right) \ge \sum\limits_{k \in {K}} {{P_{t,k}}\left( \boldsymbol{u}_t \right)\left[ {\sum\limits_{j \in k} {{r_j} - \left( {{\bar V_{t + {{1}}}}\left( {{{\boldsymbol{x}}_t}} \right) - {\bar V_{t + 1}}\left( {{{\boldsymbol{x}}_t} - {{\boldsymbol{A}}^k}} \right)} \right)} } \right]}  + {\bar V_{t + {{1}}}}\left( {{{\boldsymbol{x}}_t}} \right)\; \\ 
&\quad \forall t,{\boldsymbol{x}}_t \in {X},\boldsymbol{u}_t \in U\left( {\boldsymbol{x}}_t \right) \\
\end{align*}

将式 (\ref{eq:4-6}) 带入上面的线性规划问题，我们可以得到下面的基于仿射近似的线性规划问题(AF-LP)。这个问题的决策变量是 $(\theta,\pi)$。通过求解此问题，可以得到所有时间所有列车服务区段的机会成本。

\begin{align}
&{\text{AF\text{-}LP}}: \quad\mathop {\min }\limits_{{{\boldsymbol{\theta }},{\boldsymbol{\pi }}}} {\theta _{{1}}} + \sum\limits_i {{\pi _{{{1}},i}}{c_i}} \nonumber\\
&\text{s.t.} \nonumber\\
&{\theta _t} - {\theta _{t + 1}}{{ + }}\sum\limits_i {{\pi _{t + {{1}},i}}{Q_{t,i}}\left( \boldsymbol{u}_t \right)}  + \sum\limits_i {\left( {{\pi _{t,i}} - {\pi _{t + 1,i}}} \right){x_{t,i}}}  \ge {R_t}\left( \boldsymbol{u}_t \right)\;
\ \forall t, \boldsymbol{x}_t \in {X},\boldsymbol{u}_t \subset N\left( \boldsymbol{x}_t \right)\;  \label{eq:4-7} \\ 
&{\boldsymbol{\theta }},{\boldsymbol{\pi}} \ge 0 \nonumber 
\end{align}
\begin{itemize}
	\item 为了表述方便，令${R_t}\left( \boldsymbol{u}_t \right) = \sum\limits_{k \in K} {\sum\limits_{j \in k} {{r_j}} } {P_{t,k}}\left( \boldsymbol{u}_t \right)$ 以及 ${Q_{t,i}}\left( \boldsymbol{u}_t \right) = \sum\limits_{k \in K} {{a_{i,k}}} {P_{t,k}}\left( \boldsymbol{u}_t \right)$。
	\item 特别地，根据边界条件，本节定义${\theta _{T + 1}} = 0$ 和 ${\pi _{T + {{1}},i}} = 0\;\forall i$。
\end{itemize}

与初始的动态规划问题相比，在仿射近似线性规划中，决策变量的规模从$T \times \left| {U} \right|$ 减少到了 $T \times \left( {\left| {I} \right| + 1} \right)$。然而，对于约束(\ref{eq:4-7})的数量还是太多了。

接下来，本章首先引入(AF-LP)问题的一个简化形式，然后通过动态分解方法(dynamic disaggregated approach)求解此模型。最后，对于列生成子问题提出一个启发式算法。

\subsection{状态空间的简化}

Zhang 和 Adelman \cite{ZhangAdelman-518} 通过互补松弛性证明了定理[\ref{th1}]。定理[1]阐述了机会成本${\pi _{t,i}}$的一个性质，那就是它随着售票阶段的前进是单调递减的,如图\ref{fig:4-3}所示。

\newtheorem{theorem}{Theorem}
\begin{theorem}
存在(AF-LP)问题的一个最优解$\left( {\boldsymbol{\theta ^*}},{\boldsymbol{\pi ^*}} \right)$ 和集合 $\left\{ {\tilde t_i^*} \right\}\;\forall i$ 使得式(\ref{eq:4-8})-(\ref{eq:4-11})成立。
\label{th1}
\begin{align}
&\theta _t^* \ge \theta _{t + 1}^*\;\forall t, \label{eq:4-8} \\
&\pi _{t,i}^* = \pi _{t + 1,i}^*\;\forall i,t = {{1}}, \ldots ,\tilde t_i^* - 1 \label{eq:4-9} \\
&\pi _{t,i}^* \ge \pi _{t + 1,i}^*\;\;\forall i,t = \tilde t_i^*, \ldots ,T\label{eq:4-10} \\
&{{\boldsymbol{\theta }}^*},{{\boldsymbol{\pi }}^*} \ge 0 \label{eq:4-11}
\end{align}
\end{theorem}

\begin{figure}[htb]
\centering
\includegraphics[width=0.6\textwidth]{Fig_4-3.png}
\bicaption[fig:4-3]{机会成本单调性示意}{机会成本单调性示意}{Fig}{An example of dynamic bid price trajectories}
\end{figure}

根据(AF-LP)问题定义, 约束(\ref{eq:4-7})不能同时取等于号。如果 $\left( {\boldsymbol{\theta ^*}},{\boldsymbol{\pi ^*}} \right)$ 是(AF-LP)问题的最优解，那么根据定理[\ref{th1}]，有$\pi _{t,i}^* - \pi _{t + 1,i}^*\; \ge 0$。 注意 $\forall {{\boldsymbol{x}}_t} \in {X},\boldsymbol{u}_t \in  U\left( {\boldsymbol{x}}_t \right)\; \Leftrightarrow \forall \boldsymbol{u}_t \in U, \boldsymbol{x}_t \in X\left( \boldsymbol{u}_t \right)$， 其中 $X \left( \boldsymbol{u}_t \right)$ 表示在状态 $\boldsymbol{u}_t $下 $x$ 可行。对于任意时间段$t$，式(\ref{eq:4-12}) 成立。

\begin{align}
&\sum\limits_i {\left( {\pi _{t,i}^* - \pi _{t + 1,i}^*} \right){x_{t,i}}}  \ge \sum\limits_{i \in \mathcal{{\cal F}}\left( S \right)} {\left( {\pi _{t,i}^* - \pi _{t + 1,i}^*} \right)\;} \label{eq:4-12} \\
&\forall  \boldsymbol{u}_t \in U ,\boldsymbol{x}_t \in X\left( \boldsymbol{u}_t \right)
\nonumber
\end{align}

其中，${\mathcal{{\cal F}}\left( \boldsymbol{u}_t \right)}$ 表示在 $\boldsymbol{u}_t$ 条件下开放的产品使用的列车服务区段。
$$
{{\cal F}}\left( \boldsymbol{u} \right) = \left\{ {i\left| {\sum\limits_{j \in J} {{1_{\left\{ {i \in I_j} \right\}}} u_j \ge {{1,}}\;\forall i \in I} } \right.} \right\} \nonumber
$$

在本章中通过 $1_{\left\{ {i \in j} \right\}}$ 表示指示函数，若${i \in j}$其值为1；否则为0。综上所述，(AF-LP)问题可以简化为(RAF-LP)问题. 这两个问题的等价性被Vossen 和 Zhang \cite{VossenZhang-534}通过对其对偶问题进行Dantzig-Wolfe分解证明。

\begin{align}
& {\text{RAF\text{-}LP}}: \quad\mathop {\min }\limits_{{\boldsymbol{\theta ,\pi }}} {\theta _{{1}}} + \sum\limits_i {{\pi _{{{1}},i}}{c_i}}   \nonumber\\ 
&\text{s.t.} \nonumber\\
& {\theta _t} - {\theta _{t + 1}}{{ + }}\sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {\left[ {{\pi _{t,i}} - {\pi _{t + {{1}},i}}\left( {{{1}} - {Q_{t,i}}\left( \boldsymbol{u} \right)} \right)} \right]}  \ge {R_t}\left( \boldsymbol{u} \right)\;\forall t,\boldsymbol{u} \in U  
\label{eq:4-13}\\ 
& {\pi _{t,i}} \ge {\pi _{t + {{1}},i}}\;\forall t,i  \nonumber\\
& {\theta _t} \ge {\theta _{t + 1}}\; \forall t  \nonumber\\ 
& \boldsymbol{\theta },{\boldsymbol{\pi }} \ge 0 \nonumber  
\end{align}

在(RAF-LP)问题中，状态空间的复杂性得到的简化。(RAF-LP)问题可以采用约束生成的方法进行求解，对于每一个时间段 $t$ ，都会有一类形如(\ref{eq:4-14})的子问题。时间段 $T$ 的数量也是一个非常大的数字，根据第二章提出的 $T$ 的标定方法，一个100名潜在旅客的到达队列需要 $T$ 的量级以万计。同时，这些子问题具有分式规划的形式，属于NP-hard问题类型，没有高效的精确算法进行求解。

\begin{equation}
\mathop {\max }\limits_{\boldsymbol{u} \in U} {R_t}\left( \boldsymbol{u} \right) - \sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {\left[ {{\pi _{t,i}} - {\pi _{t + 1,i}}\left( {1 - {Q_{t,i}}\left( \boldsymbol{u} \right)} \right)} \right]}  - {\theta _t} + {\theta _{t + 1}}
\label{eq:4-14}
\end{equation}

\subsection{动态分解算法}

定理[\ref{th1}]还反映了一个重要的信息，在优解 ${\pi _{t,i}^*}$ 的时间序列中存在一个拐点${\tilde t_i^*}$。在这个拐点之前，即对于$\alpha < \min \left\{ {\tilde t_i^*} \right\}\;\forall i$，存在式(\ref{eq:4-15})。

\begin{equation}
{\theta _t^*} - {\theta _{t + 1}^*}{{ + }}\sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {{\pi _{t + {{1}},i}^*} {Q_{t,i}}\left( \boldsymbol{u} \right)} \ge {R_t}\left( \boldsymbol{u} \right)\; \quad \forall t \le \alpha ,\boldsymbol{u} \in U
\label{eq:4-15}
\end{equation}

如果假设旅客的到达过程是由多个齐次泊松过程组合而成，例如在$t=1$至$t=100$这一个时间间隔内，$\left( \rho _t,\boldsymbol{\lambda}_t \right)$是常数。注意此时期望${R_t}\left(  \boldsymbol{u}_t \right)$ 和${{Q_{t,i}}\left( \boldsymbol{u} \right)}$也是常数。令$ D_t $ 表示 $t$ 之前所有的时间间隔的数量，用$d$索引。又假设能够找到拐点之前的一个时间点$\alpha$。通过将不等式 (\ref{eq:4-15})两侧相加。令$ {\bar R _d}\left( \boldsymbol{u} \right) $ 和 $ {\bar Q _{d,i}}\left( \boldsymbol{u} \right) $ 表示阶段$d$内相同的${R_t}\left( \boldsymbol{u} \right)$ 和 ${{Q_{t,i}}\left( \boldsymbol{u} \right)}$，可以得到式(\ref{eq:4-16})。 

\begin{equation}
\frac{\bar \theta _d^* - \bar \theta _{d + 1}^*}{\varphi \left( {d + 1} \right) - \varphi \left( d \right)} + \sum\limits_{i \in \cal F\left( \boldsymbol{u} \right)} {\pi _{\alpha  + 1,i}^*{\bar Q_{d,i}}\left( \boldsymbol{u} \right)}  \ge {\bar R_d}\left( \boldsymbol{u} \right) \quad \forall d = 1, \ldots ,D_\alpha,\boldsymbol{u} \in U
\label{eq:4-16}
\end{equation}

\begin{itemize}
\item $\varphi \left( d \right)$ 表示时间间隔 $d$ 内的第一个阶段。
\item 特别地，定义$\varphi \left( {D_\alpha + 1} \right) = \alpha  + {1}$ 和 $\bar \theta _{D_\alpha + {1}}^* = \theta _{\alpha  + 1}^*$。
\item 为了表达方便，令 $\bar \theta _d^* = \theta _{\varphi \left( d \right)}^*$。
\end{itemize}

通过用式(\ref{eq:4-16})替换(RAF-LP)问题中$t \le \alpha$相关的约束, 可以得到一个状态聚合形式的(RAF-LP)问题，记作(RAF-LP-$\alpha$)问题。注意在这个问题中我们并不知道拐点，也不知道$\alpha$是否在拐点之前。

\begin{align}
& {\text{RAF}\text{-}LP\text{-}\alpha}: \quad\mathop {\min }\limits_{{\boldsymbol{\theta }},{\boldsymbol{\pi }}} {\theta _{{1}}} + \sum\limits_i {{\pi _{\alpha ,i}}{c_i}} \nonumber\\ 
&\text{s.t.} \nonumber\\
& \frac{{{{\bar \theta }_d} - {{\bar \theta }_{d + {{1}}}}}}{{\varphi \left( {d + {{1}}} \right) - \varphi \left( d \right)}}{{ + }}\sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {{\pi _{\alpha  + {{1}},i}}{{\bar Q}_{d,i}}\left( \boldsymbol{u} \right)}  \ge {{\bar R}_d}\left( \boldsymbol{u} \right) \quad \forall d = {{1}}, \ldots ,D_\alpha, \boldsymbol{u} \in U\\ 
& {\theta _t} - {\theta _{t + 1}}{{ + }}\sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {\left[ {{\pi _{t,i}} - {\pi _{t + {{1}},i}}\left( {{{1}} - {Q_{t,i}}\left( \boldsymbol{u} \right)} \right)} \right]}  \ge {R_t}\left( \boldsymbol{u} \right) \quad \forall t{{ = }}\alpha \ldots T , \boldsymbol{u}  \in U\\
&{\pi _{t,i}} \ge {\pi _{t + 1,i}}\; \quad \forall t =\alpha, \ldots ,T ,i\\
&{{\bar \theta }_d} \ge {{\bar \theta }_{t + 1}}\; \quad \forall d = 1, \ldots ,D_\alpha\\
&{\theta _t} \ge {\theta _{t + 1}}\; \quad \forall t = \alpha \ldots T \\
&{\boldsymbol{\theta }},{\boldsymbol{\bar \theta }},{\boldsymbol{\pi }} \ge 0
\end{align}

若$\left( {{\boldsymbol{\theta }},{\boldsymbol{\bar \theta }},{\boldsymbol{\pi }}} \right)$ 是(RAF-LP-$\alpha$)问题的一个解，那么可以通过式(\ref{eq:4-17}) 和 (\ref{eq:4-18})构造一个解(RAF-LP)问题的解 $\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$。
\begin{align}
{{\tilde \theta }_t} &= \left\{ {\begin{array}{*{20}{c}}
{{{\bar \theta }_{\delta \left( t \right)}} + \frac{{{{\bar \theta }_{\delta \left( t \right) + {{1}}}} - {{\bar \theta }_{\delta \left( t \right)}}}}{{\varphi \left( {d + {{1}}} \right) - \varphi \left( d \right)}} \cdot \left( {t - \varphi \left( {\delta \left( t \right)} \right)} \right)}&{t = {{1}}, \ldots ,\alpha - {{1}}}\\
{{\theta _t}}&{ t = \alpha  \ldots T }
\end{array}} \right.
\label{eq:4-17}\\
{{\tilde \pi }_{t,i}} &= \left\{ {\begin{array}{*{20}{c}}
	{{\pi _{\alpha  + {{1}},i}}}&{t = {{1}}, \ldots ,\alpha - {{1}} }\\
	{{\pi _{t,i}}}&{t = \alpha  \ldots T }
	\end{array}} \right.
\label{eq:4-18}
\end{align}
\begin{itemize}
\item ${\delta \left( t \right)}$ 表示 $ t $ 属于的时间间隔。
\end{itemize}

根据问题的构造，明显(RAF-LP-$\alpha$)是(RAF-LP)问题的一个松弛问题。假设$\alpha < \min \left\{ {\tilde t_i^*} \right\}\;\forall i$ 和 $\left( {{{\boldsymbol{\theta }}^*},{{{\boldsymbol{\bar \theta }}}^*},{{\boldsymbol{\pi }}^*}} \right)$是(RAF-LP-$\alpha$)问题的一个可行解。相关的 $\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$为(RAF-LP)问题提供了与(RAF-LP-$\alpha$)问题相同的目标函数值。所以，$\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$ 如果是一个可行解，那么它也是(RAF-LP)问题的最优解。$\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$的可行因为 (\ref{eq:4-15}) 和 (\ref{eq:4-16}) 在 $t \le \alpha$时等价。

通过以上转化，问题变为了找到一个 $\alpha  < \min \left\{ {\tilde t_i^*} \right\}\;\forall i$。查找的过程从后往前由$\alpha=T$开始. Vossen 和 Zhang \cite{VossenZhang-565} 基于此思路提出了一个动态分解方法。本章在其基础上也使用这一思想求解问题。

\begin{algorithm}[H]
\caption{动态分解方法}
\label{alg:4-1}
\begin{algorithmic}[1]

\STATE 初始化。 设置 $\alpha=T$ 并且指定搜索步长 ${\alpha _{step}}$ 和允许误差值$\mu$。

\STATE 求解(RAF-LP-$\alpha$)问题。 求解(RAF-LP-$\alpha$)问题并记录目标函数值 $V_\alpha$ 和对应的解 $\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$.

\STATE 算法停止判定。 如果 $\alpha=1$, 求解(RAF-LP)问题然后停止。如果$\alpha>1$ 并且 $ {{V_{\alpha  + {{1}}}} - {V_\alpha }} \le \mu $，停止算法； $\left( {{\boldsymbol{\tilde \theta }},{\boldsymbol{\tilde \pi }}} \right)$是最优解。否则，设置$\alpha  = \max \left\{ {{{1}},\alpha  - {\alpha _{step}}} \right\}$，返回步骤2。

\end{algorithmic}
\end{algorithm}

动态分解方法的好处是它能够求解阶段数很多的实时控制问题，并且能加快求解速度。它最差的情况是$\alpha=1$。此时，(RAF-LP-1)问题等价于(RAF-LP)问题。

\subsection{子问题求解}

(RAF-LP-$ \alpha $)问题可以通过约束生成的方法来求解，对应约束(\ref{eq:4-17})和(\ref{eq:4-18})，它有两个子问题：SUB-\uppercase\expandafter{\romannumeral1} 和 SUB-\uppercase\expandafter{\romannumeral2}。这两个子问题是具有类似结构的组合优化问题。注意决策空间大小随着产品数量的增加是指数级增加的($2 ^n$)，所以遍历产品组合的方式求解此问题是不现实的。在现有研究中求解此问题的思路主要有两种。第一种是采用启发式算法求解，如文献\parencite{BrontVulcano-483,HosseinalifamMarcotte-628}；第二种是针对特定的旅客选择模型简化求解，如文献\parencite{ZhangAdelman-518}。

\begin{align*}
&\text{SUB} \text{-} \text{\uppercase\expandafter{\romannumeral1}}:\mathop {\max }\limits_{\boldsymbol{u} \in U} {{\bar R}_d}\left( \boldsymbol{u} \right) - \sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u} \right)} {{\pi _{\alpha  + {{1}},i}}{{\bar Q}_{d,i}}\left( \boldsymbol{u} \right)}  - \frac{{{{\bar \theta }_d} - {{\bar \theta }_{d + 1}}}}{{\varphi \left( {d + 1} \right) - \varphi \left( d \right)}}\\
&\hspace{1.5cm}\forall d = 1, \ldots ,D\\
&\text{SUB} \text{-}\text{\uppercase\expandafter{\romannumeral2}}:\mathop {\max }\limits_{\boldsymbol{u} \in U} {R_t}\left( \boldsymbol{u}  \right) - \sum\limits_{i \in {{\cal F}}\left( \boldsymbol{u}  \right)} {\left[ {{\pi _{t,i}} - {\pi _{t + 1,i}}\left( {1 - {Q_{t,i}}\left( \boldsymbol{u} \right)} \right)} \right]} - {\theta _t} + {\theta _{t + 1}}\\
&\hspace{1.5cm}\forall {t = \alpha  + 1 \ldots T }
\end{align*}

在本章中，我们采用 Bront 和 Vulcano \cite{BrontVulcano-483} 的思路并且采用一种简单的启发式方法求解问题。这个方法适用于 SUB-\uppercase\expandafter{\romannumeral1}和SUB-\uppercase\expandafter{\romannumeral2}两类子问题。令$Value\left( \boldsymbol{u}  \right)$ 表示子问题的目标函数值，算法流程如下所示。

\begin{algorithm}[!h]
\caption{求解子问题的启发式算法}
\label{alg-2}
\begin{algorithmic}[1]

\STATE 设置 $\boldsymbol{u}  = \boldsymbol{0}$。

\STATE 对于每个产品-价格 $j \in {J}$， 如果 $\text{Value}\left( {\boldsymbol{u} +  \boldsymbol{e}_j } \right)>\text{Value}\left( \boldsymbol{u} \right)$，那么将更新$\boldsymbol{u} \leftarrow \boldsymbol{u} +  \boldsymbol{e}_j$。

\STATE 重复步骤 2 直到 $\boldsymbol{u}$ 不再改变或者产品-价格被完全遍历。

\end{algorithmic}
\end{algorithm}

\subsection{其它近似模型}

文献\parencite{LiuVanRyzin-429} 在研究最优控制问题时，提出了快速一种近似估计问题上界的方法。在他们研究的问题当中，假设旅客的到达是齐次泊松过程，即$\lambda_{t,l}$ 和 $\rho_t$ 均为常数。所以每个时间段的收入期望$R_t(\boldsymbol{u}_t)$ 和每种资源的消耗量期望 $Q_{t,i}(\boldsymbol{u}_t)$ 也是常数。他们将原问题转化为了一个分配问题，即决定每一种产品-价格开放状态的持续时间。开放状态$\boldsymbol{u} \in U$的持续时间用$h(\boldsymbol{u})$表示。如果假设每个产品-价格的出售量等于其期望值，每种资源的消耗量也等于其期望值。那么就可以得到如下所示的分配问题，它被称为基于选择的线性规划近似模型(CDLP)。

\begin{align}
& V^{\mathrm{CDLP}}=  \max \sum_{\boldsymbol{u} \in U} \lambda R(\boldsymbol{u}) h(\boldsymbol{u}) \nonumber \\ 
& \text { s.t. }  \nonumber \\
& \sum_{\boldsymbol{u} \in U} \lambda Q_i(\boldsymbol{u}) h(\boldsymbol{u}) \leqslant c_i, \; \forall i \in I \label{eq:4-19} \\ 
& \sum_{\boldsymbol{u} \in U} h(\boldsymbol{u}) \leqslant T \label{eq:4-20}\\ 
& h(\boldsymbol{u}) \geqslant 0 \quad \forall \boldsymbol{u} \in U \nonumber
\end{align}

其中，由于$R_t(\boldsymbol{u}_t)$ 和 $Q_{t,i}(\boldsymbol{u}_t)$ 为常数，这里省去带有时间的下标。式(\ref{eq:4-19})表示资源约束，即每种资源的使用量都不能超过初始值。式(\ref{eq:4-20})表示时间段约束，即状态的持续时间等于时间段总数。文献\parencite{LiuVanRyzin-429}证明了CDLP模型的解是原问题的一个上界。文献\parencite{BrontVulcano-483}提出了求解此问题的列生成方法。文献\parencite{VossenZhang-565}指出CDLP问题事实上是前文提到的(RAF-LP-$\alpha$)问题中$\alpha = T$的特例。虽然本章涉及的旅客到达模型和CDLP问题的假设是有区别的。本章的旅客到达模型并不是齐次泊松过程，而是几个齐次泊松过程的组合。但是CDLP问题中的近似思想仍然适用于本问题。

\section{算例}

本节通过数值实验验证不同情境下算法效率和旅客换乘带来的影响。实验的路网数据来自文献\parencite{HosseinalifamMarcotte-599}，包含5个车站和10列站站停的列车。产品和市场细分信息如数据集所示。

实验运行在一台双核 3.00 G Hz, 2 GB 内存 Windows Server 2008 操作系统的计算机上。实验代码由 C\# 编写，其中对线性规划的求解使用了CPLEX 12.5 求解器。

%\begin{figure}[htb]
%\centering
%\includegraphics[width=\textwidth]{Fig_4-4.png}
%\bicaption[fig:4-4]{Thalys高铁路网示意图}{Thalys高铁路网示意图}{Fig}{A map of Thalys high-speed railway.}
%\end{figure}

\subsection{算法性能分析}
为了对比算法的性能，本节引入了两个对照组，分别通过求解CDLP模型和RAF-LP模型。本节对算法的性能主要的考察目标是算法的时间消耗和得出的收益的期望值。CDLP 方法会通过求解线性规划模型得到静态的投标价格。它计算相对较快但是其目标函数是动态模型的一个上界。

实验的其它参数设置如下：
\begin{itemize}
\item $\rho_t$ 在 10 个间隔内取值如表\ref{tab:4-5}所示。
\item 每个间隔内都有100个阶段。
\item ${\lambda _{t,l}}$ 对任意的子市场 $ l \in L $都设置为0.05。
\item 每列车的席位数设置为5 ($c_i=5, \ \forall i \in I$)。
\end{itemize}


\begin{table}[!h]
\centering
\bicaption[tab:4-5]{$\rho_t$ 取值}{$\rho_t$ 取值}{Table}{$\rho_t$ in all time intervals}
\begin{tabular}{cccc}
\hline
间隔 & $\rho_t$ & 间隔 & $\rho_t$ \\ \hline
1        & 0.11   & 6        & 0.16   \\ 
2        & 0.12   & 7        & 0.17   \\ 
3        & 0.13   & 8        & 0.18   \\ 
4        & 0.14   & 9        & 0.19   \\ 
5        & 0.15   & 10       & 0.2    \\ \hline
\end{tabular}
\end{table}


\begin{table}[!h]
	\centering %居中
	\bicaption[tab:4-6]{动态分解算法与对照组比较}{动态分解算法与对照组比较}{Table}{Performance of dynamic disaggregation and two benchmarks}	
	\begin{tabular}{|p{0.5cm}<{\centering}|p{1.5cm}<{\centering}|p{1.5cm}<{\centering}|p{1cm}<{\centering}|p{1.5cm}<{\centering}|p{1cm}<{\centering}|p{1.5cm}<{\centering}|p{1cm}<{\centering}|}
		\hline
		\multirow{2}*{\#} & \multirow{2}*{时间间隔} & \multicolumn{2}{c|}{CDLP} & \multicolumn{2}{c|}{RAF-LP} & \multicolumn{2}{c|}{DD} \\ \cline{3-8}
		                  &                          & 时间（秒） & 值           & 时间（秒） & 值            & 时间（秒） & 值                  \\ \hline
		1                 & 1                        & 26      & 2,641           & 5,262    & 2,615            & 579      & 2,615                  \\ 
		2                 & 1-2                      & 52      & 5,497           & 10,562   & 5,468            & 602      & 5,468                  \\ 
		3                 & 1-5                      & 129     & 15,489          & 26,691   & 15,454           & 728      & 15,453                 \\ 
		4                 & 1-10                     & 1,803   & 34,221          & $>$48 h  & -                & 4,315    & 33,829                 \\ \hline
	\end{tabular}
\end{table}

这四组实验的结果如表\ref{tab:4-6}所示。注意在案例4中, (RAF-LP)问题在48小时内没有完成求解。从这个实验中可以看出，采用动态分解方法会花费比求解(RAF-LP)模型更短的时间并且得到和(RAF-LP)相同的目标函数值。

\subsection{换乘对收益的影响}

在这个实验中，通过动态分解方法产生的投标价格会被放入仿真环境中进行测试。为了简化问题，这里假设每个旅客至多换乘一次。换乘的路径如图\ref{fig:4-5}所示。图中一个换乘标示旅客从一列车换到另一列车。例如，通过换乘1/2/3，旅客可以从列车1换到列车2，或者通过换乘4/5/6从列车2换到列车3。

\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{Fig_4-5.png}
\bicaption[fig:4-5]{可行的接续示意}{可行的接续示意}{Fig}{Available transfers}
\end{figure}

换乘路径编号从201-290，它们被加入到休闲旅客的路径集中(也就是子市场3，5，7，11，13和17)。每个路径的效用设置为通过直达车的效用乘以一个0-1之间的效用系数。它表示旅客换乘的意愿：当换乘折扣效用增加，旅客会更加愿意选择换乘。表\ref{tab:4-7}展示了换乘效用系数为0.5时新增加的路径集。

\begin{table}
	\centering %居中
	\bicaption[tab:4-7]{在换乘效用系数为0.5时新增加的路径集}{在换乘效用系数为0.5时新增加的路径集}{Table}{Additional consideration set and preference vector with coefficient 0.5}	
	\begin{tabular}{|c|c|c|p{4.5cm}<{\centering}|}
		\hline
		\# &          细分市场          &      可行路径      & 偏好                                                                                     \\ \hline
		3  & PAR$\rightarrow$RTA(L) & 201$\ldots$209 & 15,10,5,1.5,2.5,10,12.5,5,2                                                            \\ \hline
		5  & PAR$\rightarrow$SCH(L) & 210$\ldots$236 & 12.5,10,2,2.5,2.5,2.5,3,3,5,
		12.5,10,2,2.5,2.5,2.5,3,3,5                             \\ \hline
		7  & PAR$\rightarrow$AMA(L) & 219$\ldots$254 & 10,1,2.5,2.5,3,3,3.5,3.5,3,
		10,1,2.5,2.5,3,3,3.5,3.5,3,
		10,1,2.5,2.5,3,3,3.5,3.5,3 \\ \hline
		11 & BRU$\rightarrow$SCH(L) & 255$\ldots$263 & 12.5,5,2.5,2.5,3,3,10,10,5                                                             \\ \hline
		13 & BRU$\rightarrow$AMA(L) & 264$\ldots$281 & 12,2,2,1.5,1.5,2.5,3,3,5,
		12,2,2,1.5,1.5,2.5,3,3,5                                   \\ \hline
		17 & RTA$\rightarrow$AMA(L) & 282$\ldots$290 & 20,5,2.5,2,1.5,2,2.5,2.5,3                                                             \\ \hline
	\end{tabular}
\end{table}

实验的其它参数设置如下所示：
\begin{itemize}
\item $\rho_t$ 的取值如表\ref{tab:4-8}所示。
\item 每个时间间隔中的阶段数设置为 1000。
\item 对于每个子市场 $ l \in L $，${\lambda _{t,l}}$ 被设置为 0.05。
\item 每列车的席位数被设置为 50 ($c_i=50, \ \forall i \in I$)。

\end{itemize}

\begin{table}[!h]
\centering
\bicaption[tab:4-8]{$\rho_t$在所有时间间隔内的取值}{$\rho_t$在所有时间间隔内的取值}{Table}{$\rho_t$ in all time intervals}
\begin{tabular}{|c|c|c|c|c|c|}
	\hline
	时间间隔 & $\rho_t$ & 时间间隔 & $\rho_t$ & 时间间隔 & $\rho_t$ \\ \hline
	   1     &   0.2    &    6     &   0.25   &    11    &   0.3    \\ \hline
	   2     &   0.21   &    7     &   0.26   &    12    &   0.31   \\ \hline
	   3     &   0.22   &    8     &   0.27   &    13    &   0.32   \\ \hline
	   4     &   0.23   &    9     &   0.28   &    14    &   0.33   \\ \hline
	   5     &   0.24   &    10    &   0.29   &    15    &   0.34   \\ \hline
\end{tabular}
\end{table}

本实验分为3组，运行了15个情景的案例。在每个情境中，我们通过动态分解方法计算了一组投标价格并进行了购票仿真。作为对比，本实验引入了先到先服务规则(First come first serve, FCFS)作为对照组。每个情境下运行仿真20,000次。

\begin{table}[!h]
	\centering %居中
	\bicaption[tab:4-9]{仿真结果}{仿真结果}{Table}{Results of the simulation}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		分组 & 时间间隔 & $\gamma$ & 情景 & 换乘效用系数 & UB      & BPC     & FCFS    \\ \hline
		1  & 1-5  &   0.9    & 1  &   0    & 268,330 & 245,640 & 241,468 \\ \hline
		1  & 1-5  &   0.9    & 2  &  0.25  & 268,932 & 246,642 & 241,650 \\ \hline
		1  & 1-5  &   0.9    & 3  &  0.50  & 269,501 & 243,222 & 241,502 \\ \hline
		1  & 1-5  &   0.9    & 4  &  0.75  & 269,974 & 246,130 & 241,221 \\ \hline
		1  & 1-5  &   0.9    & 5  &   1    & 270,499 & 247,928 & 241,269 \\ \hline
		2  & 1-10 &   2.1    & 6  &   0    & 364,659 & 322,542 & 289,857 \\ \hline
		2  & 1-10 &   2.1    & 7  &  0.25  & 366,972 & 331,810 & 288,703 \\ \hline
		2  & 1-10 &   2.1    & 8  &  0.50  & 368,453 & 302,965 & 287,883 \\ \hline
		2  & 1-10 &   2.1    & 9  &  0.75  & 370,544 & 323,845 & 287,283 \\ \hline
		2  & 1-10 &   2.1    & 10 &   1    & 363,596 & 325,207 & 287,328 \\ \hline
		3  & 1-15 &   3.5    & 11 &   0    & 416,463 & 327,537 & 308,457 \\ \hline
		3  & 1-15 &   3.5    & 12 &  0.25  & 419,284 & 336,568 & 306,760 \\ \hline
		3  & 1-15 &   3.5    & 13 &  0.50  & 414,605 & 320,615 & 305,702 \\ \hline
		3  & 1-15 &   3.5    & 14 &  0.75  & 410,818 & 354,766 & 304,846 \\ \hline
		3  & 1-15 &   3.5    & 15 &   1    & 415,310 & 369,910 & 304,871 \\ \hline
	\end{tabular}
\end{table}

实验结果如表\ref{tab:4-9}所示。表格说明如下：

\begin{itemize}
\item 列UB表示售票收入的期望$V_1(\boldsymbol{c})$，它是动态规划问题的目标函数值。
\item 列BPC和FCFS表示通过投标价格模式和先到先服务模式仿真的售票收入平均值。
\item 列$\gamma$表示文献\parencite{ZhangAdelman-518}中提的负载率指标，它表示供求之间的匹配程度。负载率可以通过式(\ref{eq:4-25})计算，其中${\boldsymbol{u}^*} \in \mathop {\arg \max }\limits_{\boldsymbol{u} \in U} \sum\limits_{j \in J} {{P_j}\left( \boldsymbol{u} \right)}  {r_j} {u_j}$。
\begin{equation}
\gamma { = }\frac{{\sum\limits_t^\tau  {{\rho _t}\sum\limits_{k \in {\boldsymbol{u}^*}} {\sum\limits_i {{a_{ik}}{P_k}\left( {{\boldsymbol{u}^*}} \right)} } } }}{{\sum\limits_i {{c_i}} }}
\label{eq:4-25}
\end{equation}
\end{itemize}

一个很直接的观测结果是通过采用投标价格控制带来的平均收益明显高于采用先到先服务的客票销售规则。实验数据对比如表
\ref{tab:4-10}所示。其中，在高负载率的情况下，采用投标价格对收入带来的提升更加明显，具体参考分组2($\gamma=2.1$)和分组3($\gamma=3.5$)的实验结果。
	 
\begin{table}[!h]
\centering
\bicaption[tab:4-10]{实验结果对比}{实验结果对比}{Table}{Comparsion of average revenue}
\begin{tabular}{|c|c|c|c|c|c|}
	\hline
	\multicolumn{2}{|c|}{分组 1} & \multicolumn{2}{c|}{分组 2} & \multicolumn{2}{c|}{分组 3} \\ \hline
	情景 &            增量            & 情景 &           增量            & 情景 &           增量            \\ \hline
	1  &          4,172           & 6  &         32,685          & 11 &         19,080          \\ \hline
	2  &          4,992           & 7  &         43,107          & 12 &         29,808          \\ \hline
	3  &          1,720           & 8  &         15,082          & 13 &         14,913          \\ \hline
	4  &          4,909           & 9  &         36,562          & 14 &         49,920          \\ \hline
	5  &          6,659           & 10 &         37,879          & 15 &         65,039          \\ \hline
\end{tabular}
\end{table}

图\ref{fig:4-6}展示了旅客换乘带来的影响。从图中可以观察到，随着负载率的提高，收入的震荡更加明显。通过这一分析可以得到一个启示：当需求旺盛的时候需要仔细考虑旅客换乘。

\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{Fig_4-6.png}
\bicaption[fig:4-6]{实验结果对比箱线图}{实验结果对比箱线图}{Fig}{The box-plot of revenue in each group}
\end{figure}

另一个观测结果是平均收入并不是随着换乘效用的增加而持续增加的。产生这种现象的原因是换乘会通过两条链影响售票结果，如图\ref{fig:4-7}所示。 当旅客更愿意换乘时，在直达产品被销售完之后，能构建换乘的产品的销量也增加了。但另一方面，对于休闲旅客，如果可以换乘，他们就不愿意花更多的钱去买价格稍贵的直达车票了。除此之外，由于本章提出的算法中嵌套了启发式算法，所以在实验中使用的并不一定是最优解，进而给实验结果带来误差。
 
\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{Fig_4-7.png}
\bicaption[fig:4-7]{换乘对收益的两面性示意图}{换乘对收益的两面性示意图}{Fig}{The two-sided effect of transfers on revenue}
\end{figure}
 
表\ref{tab:4-11}中计算了四个反映换乘影响的指标：旅客流失比例(旅客放弃铁路出行的比例)、换乘旅客比例(出行旅客中换乘旅客的比例)、换乘收入比例(来自换乘旅客的售票收入占总收入的比例)、高价票收入比例(来自高价格车票的收入占总收入的比例)。表\ref{tab:4-11}反映了换乘旅客数量随着负载率的增加而降低，高价格车票的销售收入反而增加。在分组1实验中随着换乘效用系数的增加的乘客数目明显上升。它反映了低负荷时客流的变化规律。

\begin{table}[H]
	\centering 
	\bicaption[tab:4-11]{售票的四个指标}{售票的四个指标}{Table}{Four indicators from ticket selling results}
	\begin{tabular}{|c|c|p{2cm}<{\centering}|p{2cm}<{\centering}|p{2cm}<{\centering}|p{2cm}<{\centering}|p{2cm}<{\centering}|}
		\hline
		分组 & 情景 & 换乘效用系数 & 旅客流失比例  & 换乘旅客比例 & 换乘收入比例  & 高价票收入比例 \\ \hline
		1  & 1  &   0    & 20.33\% & -      & -       & 77.20\% \\ \hline
		1  & 2  &  0.25  & 20.12\% & 3.88\% & 4.42\%  & 75.98\% \\ \hline
		1  & 3  &  0.50  & 20.06\% & 8.88\% & 9.87\%  & 71.19\% \\ \hline
		1  & 4  &  0.75  & 20.09\% & 8.31\% & 9.51\%  & 73.47\% \\ \hline
		1  & 5  &   1    & 20.05\% & 9.41\% & 10.88\% & 72.70\% \\ \hline
		2  & 6  &   0    & 54.23\% & -      & -       & 94.46\% \\ \hline
		2  & 7  &  0.25  & 52.10\% & 0.24\% & 0.09\%  & 94.50\% \\ \hline
		2  & 8  &  0.50  & 54.10\% & 0.24\% & 0.10\%  & 94.98\% \\ \hline
		2  & 9  &  0.75  & 53.13\% & 0.01\% & 0.02\%  & 95.46\% \\ \hline
		2  & 10 &   1    & 52.07\% & 1.15\% & 1.36\%  & 93.00\% \\ \hline
		3  & 11 &   0    & 70.06\% & -      & -       & 96.92\% \\ \hline
		3  & 12 &  0.25  & 69.40\% & 0.01\% & 0.01\%  & 97.61\% \\ \hline
		3  & 13 &  0.50  & 71.61\% & 0.02\% & 0.02\%  & 97.68\% \\ \hline
		3  & 14 &  0.75  & 69.99\% & 0.01\% & 0.01\%  & 99.50\% \\ \hline
		3  & 15 &   1    & 69.43\% & 0.01\% & 0.02\%  & 97.83\% \\ \hline
	\end{tabular}
\end{table}

\section{本章小节}

本章研究了基于动态投标价格的铁路动态价格的制定方法，通过构建动态规划模型求解动态投标价格，并且采用线性近似目标函数进行求解。为了求解近似线性规划问题，设计了一个动态聚合的启发式方法。相比于原问题，近似问题有效减少了变量和约束的数量，能够提高问题求解的速度。

通过仿真实验，本章评价了动态价格在不同需求强度和旅客的不同换乘意愿下的售票收入。在旅客换乘意愿变化时，售票收入会出现波动，但是没有一个明显的趋势。这是因为换乘意愿的增加对客票收入的影响是有两面性的：一方面，换乘能够带来的出行的旅客数增加，从而提高收入；另一方面，换乘会让原有购买高价票的旅客转向购买低价票换乘出行，降低收入。